package thired.class04_mergesort;

public class Class03_BiggerThanRightTwice {
    public static int reversePairs(int[] nums) {
    if(nums == null || nums.length < 2){
        return 0;
    }
    return process(nums,0,nums.length - 1);
    }

    public static int process(int[] nunms,int l,int r){
        if(l==r){
            return 0;
        }
        int m = l + ((r-l) >> 1);
        return process(nunms,l,m)+
                process(nunms,m + 1,r)+
                merge(nunms,l,m,r);
    }

    public static int merge(int[] nums,int l,int m,int r){
        int[] help = new int[r- l + 1];
        int ans = 0;
        int window = m + 1;
        for (int i = l; i <= m; i++) {
            while(window <= r && nums[i] > 2 * nums[window]){
                window++;
            }
            ans += window-m-1;
        }
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        while(p1 <= m && p2 <= r){
            help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while(p1 <= m){
            help[i++] = nums[p1++];
        }
        while (p2 <= r){
            help[i++] = nums[p2++];
        }
        for (int j = l; j <= r; j++) {
            nums[j] = help[j - l];
        }
        return ans;
    }
}
